#include <iostream>

#include "common_list.h"

using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    ListNode *Merge(ListNode *pHead1, ListNode *pHead2) {
        if (!pHead1) {
            return pHead2;
        } else if (!pHead2) {
            return pHead1;
        }

        ListNode *tmp = new ListNode;
        ListNode *ptr = tmp;
        while (pHead1 && pHead2) {
            if (pHead1->val < pHead2->val) {
                ptr->next = pHead1;
                pHead1    = pHead1->next;
            } else {
                ptr->next = pHead2;
                pHead2    = pHead2->next;
            }
            ptr = ptr->next;
        }
        ptr->next = pHead1 ? pHead1 : pHead2;
        return tmp->next;
    }
};

int main(void) {
    int val1[] = {1, 4, 6, 8};
    int val2[] = {2, 5, 7, 9};

    auto head1 = generate_list_val(sizeof(val1) / sizeof(int), val1);
    print_list(head1);
    auto head2 = generate_list_val(sizeof(val2) / sizeof(int), val2);
    print_list(head2);
    auto headnew = (new Solution())->Merge(head1, head2);
    print_list(headnew);
    return 0;
}